import java.util.Arrays;

public class productExceptSelf {
    /**
     * 除自身以外的数组的乘积
     */
    // 由于是不能使用除法操作，所有采用的是分治
    // 本质上就是分治算区间的乘法，后来直接两者合并后相乘即可
    public static int [] method(int[] nums){
        int n = nums.length;
        // 采取分治思想，左乘积、右乘积
        int pre = 1;
        int suf = 1;
        // 定义结果数组
        int[] res=new int[n];
        for(int r=0;r<n;r++){
            res[r] = 1;
        }

        // 遍历数组，同时从两边向中间计算乘积结果
        for(int i=0,j=n-1;i<n;i++,j--){
            res[i] *=pre;
            res[j] *=suf;
            pre*=nums[i];
            suf*=nums[j];
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums={1,2,3,4};
        System.out.println(Arrays.toString(method(nums)));
    }
}
